1. Field of the Invention
The present invention relates to mutual division circuits and, more particularly, is directed to an Euclidean division circuit for carrying out Euclidean mutual division.
2. Description of the Prior Art
When an error correction system is realized by using an error correction code represented by a Bose-Chaundhuri-Hocquenghem (BCH) code and a Reed-Solomon code, a means for obtaining an error locator polynomial from a syndrome generated by a reception signal plays the most important role.
As a method for realizing this process, a method using an Euclidean mutual division algorithm is widely known.
The Euclidean mutual division method is generally known as an algorithm through which the most common divisor of two polynomials is obtained. In the error correction code, the error locator polynomial can be calculated from a syndrome by the skillful application of a calculation procedure that is used in the process of the Euclidean mutual division method.
The calculation process of the Euclidean mutual division method has the advantage such that it can be composed of a systolic-array architecture wherein it can be realized by cascading a plurality of relatively simple calculation units (hereinafter referred to as "mutual division unit").
An example that can realize an algorithm of Euclidean mutual division method by means of the systolic array has been proposed by Howard M. Shao et. al. (see Howard M. Shao et. al. "A VLSI Design of a Pipeline Reed-Solomon Decoder" IEEE Trans. on Computers Vol.C-34 May, 1985). This method will hereinafter be referred to as a "method A". The method A has defects such that its algorithm is not perfect and that each unit needs two multipliers for a finite field. Thus, when a system that needs a high speed real processing is constructed based on this method A, its circuit scale is increased
As improved methods of the above method A, we have previously proposed a method (see U.S. patent application Ser. No. 07/623,235), issued on Feb. 9, 1993 as U.S. Pat. No. 5,185,711. This previously-proposed method will be referred to as a "method B" in the description which follows. This method B employs an improved algorithm of the preceding algorithm disclosed in the aforementioned method A and replaces two finite field multipliers in the mutual division unit with a multiplier for a finite field and a divider for a finite field. Further, the method B replaces the finite field dividers used in a plurality of cascaded mutual division units with a divider for a finite field. Hence, a circuit scale can be reduced.
However, the method B needs a complex control circuit that is needed to commonly use the divider for a finite field from a plurality of mutual division units so that an operation speed cannot be increased. Further, although the divider for a finite field is used commonly, each mutual division unit needs a circuit for judging operation from the degree of polynomial and a control circuit so that the circuit scale is increased a little.
The method B will be described below in detail.
An error correction technique will be described first.
This system is effective not only for error correction but also all systems which are needed in order to realize the Euclidean mutual division method at high speed. This method when applied to the error correction method using Reed-Solomon code will be described.
In the description which follows, exponents are depicted by underlined letters following " " and suffixes are depicted by underlined letters having no " ".
Let us consider an error correction system having a code length of n which can correct an error of t symbols by using a finite field of GF (2 m). Let it be assumed that a j expresses that an error locator is j'th position where the head of code is selected to be 0th position. Then, if the code has m errors in total, then total errors of the code will be described by error locator Xi (i=1, . . . , m) and error pattern yi (i=1, . . . , m). That is, if there are m (m.ltoreq.2t) errors in total, then m sets of (Xi, Yi) are required.
A polynomial known as an error locator polynomial .sigma.(X) is defined by using this error locator Xi (i=1, . . . , m). The error locator polynomial .sigma.(X) becomes 0 if error locator X=Xi -1 where i=1, . . . , m. ##EQU1##
Coefficient of .sigma.(X) is expressed as: EQU .sigma.(X)=1+.sigma..sub.1 X+.sigma..sub.2 X.sup.2 + . . . .sigma..sub.a X.sup.a ( 2)
Further, using the error locator polynomial .sigma.(X) and a syndrome polynomial S(X), an error evaluator polynomial .omega.(X) is defined as: EQU .omega.(X)=S(X).sigma.(X)(mod X.sup.2t) (3)
The error correction process will next be described in the order of steps.